package 回溯;

public class LeetCode79_单词搜索 {
    private int[][] directions = {{1,0}, {-1,0}, {0,1}, {0,-1}};
    private char[][] board;
    private String word;
    public boolean exist(char[][] board, String word) {
        if(board.length == 0 || board == null || word == null) {
            return false;
        }
        int h = board.length;
        int w = board[0].length;
        boolean[][] visited = new boolean[h][w];
        this.board = board;
        this.word = word;

        for(int i = 0; i < h; i++) {
            for(int j = 0; j < w; j++) {
                boolean flag = backtracking(visited, i, j,0);
                if(flag) {
                    return true;
                }
            }
        }
        return false;
    }

    public boolean backtracking(boolean[][] visited,int i, int j, int k) {
        if(board[i][j] != word.charAt(k)) {
            return false;
        } else if(k == word.length()-1) {
            return true;
        }
        visited[i][j] = true;

        boolean resault = false;

        for(int[] dir : directions) {
            int newi = i + dir[0], newj = j + dir[1];
            if(newi >= 0 && newi < board.length && newj >= 0 && newj < board[0].length) {
                if(!visited[newi][newj]) {
                    boolean flag = backtracking(visited, newi, newj, k+1);
                    if(flag) {
                        resault = true;
                        break;
                    }
                }
            }
        }
        visited[i][j] = false;
        return resault;
    }
}
